#include "regex_parser.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include "stack.h"
#include "regex_vm.h"

ast_node *make_ast_node(enum ast_node_type t)
{
	ast_node *node = (ast_node *)malloc(sizeof(ast_node));
	node->c = 0;
	node->type = t;
	node->left = NULL;
	node->right = NULL;
	return node;
}
ast_node *parse_regex(unsigned char *regex, int length)
{
	int index = 0;
	ast_node *tmp = NULL;
	ast_node *tmp1 = NULL;
	ast_node *tmp2 = NULL;
	Stack *stack = initStack();
	for (index = 0; index < length; ++index)
	{
		if (regex[index] == '\\')
		{
			++index;
			if (regex[index] == 'w')
			{
				if (tmp == NULL)
				{
					tmp = make_ast_node(t_word);
				}
				else
				{
					tmp1 = make_ast_node(t_con);
					tmp1->left = tmp;
					tmp1->right = make_ast_node(t_word);
					tmp = tmp1;
					tmp1 = NULL;
				}
			}
			if (regex[index] == 's')
			{
				if (tmp == NULL)
				{
					tmp = make_ast_node(t_space);
				}
				else
				{
					tmp1 = make_ast_node(t_con);
					tmp1->left = tmp;
					tmp1->right = make_ast_node(t_space);
					tmp = tmp1;
					tmp1 = NULL;
				}
			}
			if (regex[index] == 'S')
			{
				if (tmp == NULL)
				{
					tmp = make_ast_node(t_nonespace);
				}
				else
				{
					tmp1 = make_ast_node(t_con);
					tmp1->left = tmp;
					tmp1->right = make_ast_node(t_nonespace);
					tmp = tmp1;
					tmp1 = NULL;
				}
			}
			else if (regex[index] == 'd')
			{
				if (tmp == NULL)
				{
					tmp = make_ast_node(t_number);
				}
				else
				{
					tmp1 = make_ast_node(t_con);
					tmp1->left = tmp;
					tmp1->right = make_ast_node(t_number);
					tmp = tmp1;
					tmp1 = NULL;
				}
			}
			else if (regex[index] == '['
			||regex[index] == ']'
			||regex[index] == '('
			||regex[index] == ')'
			||regex[index] == '.'
			||regex[index] == '+'
			||regex[index] == '*'
			||regex[index] == '?'
			||regex[index] == '.'){
				tmp = make_ast_node(t_char);
				tmp->c=regex[index];
			}
			else
			{
			}
		}
		else if (regex[index] == '|')
		{
			if (tmp == NULL)
			{
				//error
			}
			else
			{
				tmp1 = make_ast_node(t_split);
				tmp1->left = tmp;
				tmp = tmp1;
				tmp1 = NULL;
				push(stack, tmp);
				tmp = NULL;
			}
		}
		else if (regex[index] == '(')
		{
			if (tmp != NULL)
			{
				push(stack, tmp);
				tmp = NULL;
			}
			push(stack, make_ast_node(t_lp));
		}
		else if (regex[index] == '.')
		{
			if (tmp == NULL)
			{
				tmp = make_ast_node(t_any);
			}
			else
			{
				tmp1 = make_ast_node(t_con);
				tmp1->left = tmp;
				tmp1->right = make_ast_node(t_any);
				tmp = tmp1;
				tmp1 = NULL;
			}
		}
		else if (regex[index] == ')')
		{
			//printf("stack size :%d",stackSize(stack));
			while (stackSize(stack) > 0)
			{
				tmp1 = (ast_node *)pop(stack);
				if (tmp1->type == t_lp)
				{
					//push(stack, tmp);
					break;
				}
				if (tmp == NULL)
				{
					//error
					printf("tmp is NULL\n");
				}
				else
				{
					if (tmp1->type == t_split)
					{
						tmp1->right = tmp;
						tmp2 = tmp1;
					}
					else
					{
						tmp2 = make_ast_node(t_con);
						tmp2->right = tmp;
						tmp2->left = tmp1;
					}
					tmp = tmp2;
					tmp1 = NULL;
					tmp2 = NULL;
				}
			}
			push(stack, tmp);
			tmp = NULL;
		}
		else if (regex[index] == '+')
		{
			if (tmp == NULL)
			{
				tmp = make_ast_node(t_plus);
				tmp->left = (ast_node *)pop(stack);
				//display_ast(tmp->left,0);
			}
			else
			{
				tmp1 = make_ast_node(t_plus);
				if (tmp->right == NULL)
				{
					tmp1->left = tmp;
					tmp = tmp1;
				}
				else
				{
					tmp1->left = tmp->right;
					tmp->right = tmp1;
				}
				tmp1 = NULL;
			}
		}
		else if (regex[index] == '*')
		{
			if (tmp == NULL)
			{
				tmp = make_ast_node(t_plus);
				tmp->left = (ast_node *)pop(stack);
				//display_ast(tmp->left,0);
			}
			else
			{
				tmp1 = make_ast_node(t_multi);
				if (tmp->right == NULL)
				{
					tmp1->left = tmp;
					tmp = tmp1;
				}
				else
				{
					tmp1->left = tmp->right;
					tmp->right = tmp1;
				}
				tmp1 = NULL;
			}
		}
		else
		{
			if (tmp == NULL)
			{
				tmp = make_ast_node(t_char);
				tmp->c = regex[index];
			}
			else
			{
				tmp1 = make_ast_node(t_con);
				tmp1->left = tmp;
				tmp1->right = make_ast_node(t_char);
				tmp1->right->c = regex[index];
				tmp = tmp1;
				tmp1 = NULL;
			}
		}
	}
	while (stackSize(stack) > 0)
	{
		tmp2 = (ast_node *)pop(stack);
		if (tmp == NULL)
		{
			tmp = tmp2;
		}
		else
		{
			if (tmp2->type == t_split)
			{
				tmp2->right = tmp;
				tmp1 = tmp2;
			}
			else
			{
				tmp1 = make_ast_node(t_con);
				tmp1->right = tmp;
			}
			tmp = tmp1;
		}
		tmp1 = NULL;
		tmp2 = NULL;
	}
	releaseStack(stack);
	return tmp;
}
void display_ast(ast_node *root, int blk)
{
	if (root == NULL)
	{
		return;
	}
	for (int i = 0; i < blk; i++)
		printf("    "); //缩进
	switch (root->type)
	{
	case t_char:
		printf("|—<char %c>\n", root->c);
		break;
	case t_con:
		printf("|—<con>\n");
		break;
	case t_multi:
		printf("|—<*>\n");
		break;
	case t_plus:
		printf("|—<+>\n");
		break;
	case t_number:
		printf("|—<num>\n");
		break;
	case t_split:
		printf("|—<|>\n", root->c);
		break;
	case t_word:
		printf("|—<word>\n");
		break;
	case t_any:
		printf("|—<any>\n");
		break;
	case t_space:
		printf("|—<space>\n");
		break;
	case t_nonespace:
		printf("|—<nonespace>\n");
		break;
	}
	display_ast(root->left, blk + 1); //打印子树，累加缩进次数
	display_ast(root->right, blk + 1);
}

instruction *regex_compile(ast_node *root)
{
	/**
	a		    	char a
	e1e2		    codes for e1
					codes for e2
	e1|e2		    split L1, L2
				L1: codes for e1
					jmp L3
				L2: codes for e2
				L3:
	e?		    	split L1, L2
				L1: codes for e
				L2:
	e*			L1: split L2, L3
				L2: codes for e
					jmp L1
				L3:
	e+			L1: codes for e
					split L1, L3
				L3:
	*/
	instruction *tmp = NULL;
	instruction *end = NULL;
	instruction *end1 = NULL;
	if (root == NULL)
	{
		return NULL;
	}
	switch (root->type)
	{
	case t_char:
		//display_ast(root,0);
		tmp = make_instruction(i_char);
		tmp->c = root->c;
		//display_instruction(tmp);
		return tmp;
		break;
	case t_con:
		tmp = regex_compile(root->left);
		end = tmp;
		while (end->next != NULL)
		{
			end = end->next;
		}
		//display_ast(root->right,0);
		//display_instruction(regex_compile(root->right));
		end->next = regex_compile(root->right);
		//display_instruction(tmp);
		//display_instruction(end->next);
		return tmp;
		break;
	case t_multi:
		tmp = make_instruction(i_split);
		tmp->op1 = regex_compile(root->left);
		//tmp->op2=regex_compile(root->right);
		tmp->next = tmp->op1;
		end = tmp->op1;
		while (end->next != NULL)
		{
			end = end->next;
		}
		end->next = make_instruction(i_jmp);
		end->next->op1 = tmp;
		end->next->next = make_instruction(i_nop);
		tmp->op2 = end->next->next;
		return tmp;
		break;
	case t_plus:
		tmp = regex_compile(root->left);
		end = tmp;
		while (end->next != NULL)
		{
			end = end->next;
		}
		end->next = make_instruction(i_split);
		end->next->op1 = tmp;
		//end->next->op2 = regex_compile(root->right);
		end->next->op2 = make_instruction(i_nop);
		end->next->next = end->next->op2;
		return tmp;
		break;
	case t_number:
		tmp = make_instruction(i_number);
		return tmp;
		break;
	case t_space:
		tmp = make_instruction(i_space);
		return tmp;
		break;
	case t_nonespace:
		tmp = make_instruction(i_nonespace);
		return tmp;
		break;
	case t_any:
		tmp = make_instruction(i_any);
		return tmp;
		break;
	case t_split:
		tmp = make_instruction(i_split);
		tmp->op1 = regex_compile(root->left);
		tmp->op2 = regex_compile(root->right);
		tmp->next = tmp->op1;
		end = tmp->op1;
		while (end->next != NULL)
		{
			end = end->next;
		}
		end->next = make_instruction(i_jmp);
		end->next->op1 = make_instruction(i_nop);
		;
		end->next->next = tmp->op2;
		end1 = end->next;
		while (end1->next != NULL)
		{
			end1 = end1->next;
		}
		end1->next = end->next->op1;
		return tmp;
		break;
	case t_word:
		tmp = make_instruction(i_word);
		return tmp;
		break;
	}
	return NULL;
}

void display_instruction(instruction *start)
{
	instruction *tmp = start;
	while (tmp != NULL)
	{
		switch (tmp->type)
		{
		case i_char:
			printf("[%p]char %c\n", tmp, tmp->c);
			break;
		case i_word:
			printf("[%p]word\n", tmp);
			break;
		case i_number:
			printf("[%p]number\n", tmp);
			break;
		case i_split:
			printf("[%p]split %p %p\n", tmp, tmp->op1, tmp->op2);
			break;
		case i_jmp:
			printf("[%p]jmp %p\n", tmp, tmp->op1);
			break;
		case i_nop:
			printf("[%p]nop\n", tmp);
			break;
		case i_any:
			printf("[%p]any\n", tmp);
			break;
		case i_match:
			printf("[%p]match\n", tmp);
			break;
		}
		tmp = tmp->next;
	}
}